package com.example.leetcode;

/**
 * 动态规划 ** 难点 ** 参考题解
 * 统计全为 1 的正方形子矩阵
 * 右下角 最大边长 与以此右下角正方形关系 (考虑是否有重复)
 */
public class Demo1277 {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n =matrix[0].length;
        int ans[][]=new int[m+1][n+1];
        int res=0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j]==1){
                    if ((i-1>=0 && matrix[i-1][j]==0) || (j-1>=0 && matrix[i][j-1]==0) ){
                        ans[i+1][j+1]=1;
                    }else {
                        ans[i+1][j+1]=Math.min(Math.min(ans[i][j],ans[i][j+1]),ans[i+1][j])+1;
                    }
                    res+=ans[i+1][j+1];
                }
            }
        }
        return res;
    }
}
